In data broadcasting using TCP/IP (Transmission Control Protocol/Internet Protocol) or UDP/IP (User Datagram Protocol/Internet Protocol), such as the Internet, a technique is used in which a sender sends a receipt acknowledgement request to receivers, and each receiver returns a receipt acknowledgement (if the receiver has received all the packets) or retransmission requests (if the receiver failed to receive all the packets) so that loss of transmitted packets (data blocks) can be addressed. Then, the sender, which received the reply message(s), retransmits specified data blocks to the receivers that have sent the retransmission requests, and sends a receipt acknowledgement request as before. Repeating data transmission and a retransmission request in this manner ensures that all the data is eventually received by every receiver, and high reliability of data communication can be maintained.
However, in broadcasting, there are a plurality of receivers for one sender. This may cause congestion of reply messages from the receivers after the sender sends a receipt acknowledgement request. The congestion of reply messages may block execution of other applications or may cause overflow of the communication route with possible loss of reply data.
To avoid such congestion of reply messages, a technique involving setting of a backoff time is employed. That is, the timing with which a reply message is sent from each receiver is made to be a random timing within the backoff time, so that the timings of the receivers are shifted from each other. The timings with which the sender receives the reply messages become random within the backoff time, and this disperses the traffic and reduces the load on the communication route, thereby avoiding the above-mentioned problem.
However, in large-scale broadcasting involving a large amount of reply messages in total, the above-mentioned technique of reply timing dispersion is not sufficient to solve the problem. That is, the above technique has a problem of the increased total amount of reply messages proportional to the number of receivers, and a problem of poor utilization of the bandwidth of return lines.
The loss rate of transmitted blocks (the error rate) depends on a communication system or an actual environment but not on the number of receivers. Accordingly, given a certain error rate, the total number of lost blocks increases in proportion to increase in the number of receivers. Because retransmission requests for lost blocks are included in a reply message and sent to the sender, the total amount of reply messages increases as the total number of lost blocks increases. The conventional technique of reply timing dispersion only shifts the timings but cannot reduce the total amount of reply messages.
Further, the conventional backoff time is obtained by the total amount of reply messages divided by the bandwidth. Because the total amount of reply messages is the product of the average reply message length and the number of receivers (senders of the reply messages), calculation of the backoff time requires the average reply message length to be assumed. Because a reply message includes retransmission requests and the retransmission requests include numbers of blocks requested to be retransmitted, the reply message length will be long if many blocks are requested to be retransmitted (i.e., if the error rate is high). In contrast, the reply message length will be short if the error rate is low. In other words, the reply message length depends on the error rate. If the actual error rate is higher than the assumed error rate, the average reply message length will be longer than the assumed length, which may cause traffic congestion and possibly leads to overflow. In contrast, if the actual error rate is lower than the assumed error rate, the average reply message length will be shorter than the assumed length, which prevents effective use of the bandwidth of the communication route. That is, communication is completed with delay due to the backoff time that is set unnecessarily longer, although otherwise the processing could be completed earlier. In addition, the error rate may vary, for example in the range from 10% to 0.01% depending on the whether in the case of satellite broadcasting. Therefore, assumption of an optimal error rate in advance is difficult in reality.
An object of the invention is to provide a technique to reduce the total amount of reply messages in broadcasting. Another object of the invention is to provide a technique to make effective use of the bandwidth of a communication route without assuming the error rate in advance. Still another object of the invention is to provide a technique to enhance reliability and efficiency of broadcasting.
In this connection, there is a technique to disperse congesting reply messages, in which retransmission requests are collected once for every fewer blocks transmitted. However, this technique has a problem that the total amount of retransmission requests including their headers increases in contrast. Further, there is a technique to reduce the total amount of reply messages, in which receivers broadcast reply messages and they reduce elements included in their own reply message in response to receipt of the reply messages. However, this technique requires that every receiver has a system capable of broadcasting, and it also involves a problem of increased data distribution time in the cases of systems such as a satellite system. Other techniques to reduce the total amount of reply messages includes a technique using a network topology having a tree-structure in which receivers located at intermediate nodes collect reply messages to reduce redundant elements. However, this technique has a problem that it is limited by a topology. This invention achieves the above-mentioned objects without these limitations.